package own.stu.jobgib.playown.alg.solution.backtrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 排列  子集
 */
public class Permutation {

    public static void main(String[] args) {
        Permutation p = new Permutation();
//        System.out.println(p.permute(new int[]{1, 2, 3}));
//        System.out.println(p.permuteUnique(new int[]{1, 2, 3}));
//        System.out.println(p.permuteUnique(new int[]{1, 1, 2}));

//        System.out.println(p.subsets(new int[]{1, 2, 3}));
//        System.out.println(p.subsets(new int[]{1}));

//        System.out.println(p.subsetsWithDup(new int[]{1, 2, 2}));

//        System.out.println(p.letterCasePermutation("a1b2"));
//        System.out.println('a' - 'A');

//        System.out.println(p.toList("{a,b}{c,d}{e,f}x"));

        System.out.println(p.bracketExpansion("{a,b}{c,d}{e,f}x"));
    }

    /**
     * 46. 全排列
     * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
     * <p>
     * 示例 1：
     * <p>
     * 输入：nums = [1,2,3]
     * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return ans;
        }

        permuteHelper(ans, nums, new boolean[nums.length], new ArrayList<Integer>());

        return ans;
    }

    private void permuteHelper(List<List<Integer>> ans, int[] nums, boolean[] visited, List<Integer> list) {
        if (list.size() == nums.length) {
            ans.add(new ArrayList<>(list));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) {
                continue;
            }
            visited[i] = true;
            list.add(nums[i]);
            permuteHelper(ans, nums, visited, list);
            visited[i] = false;
            list.remove(list.size() - 1);
        }
    }

    /**
     * 47. 全排列 II
     * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
     * <p>
     * 示例 1：
     * <p>
     * 输入：nums = [1,1,2]
     * 输出：
     * [[1,1,2], [1,2,1], [2,1,1]]
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return ans;
        }

        Arrays.sort(nums);
        permuteUniqueHelper(ans, nums, new boolean[nums.length], new ArrayList<Integer>());
        return ans;
    }

    private void permuteUniqueHelper(
            List<List<Integer>> ans, int[] nums, boolean[] visited, List<Integer> list) {
        if (list.size() == nums.length) {
            ans.add(new ArrayList<>(list));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) {
                continue;
            }
            // 树层去重
            if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
                continue;
            }
            visited[i] = true;
            list.add(nums[i]);
            permuteUniqueHelper(ans, nums, visited, list);
            visited[i] = false;
            list.remove(list.size() - 1);
        }
    }

    /**
     * 31. 下一个排列
     * 整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。
     * <p>
     * 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
     * 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
     * <p>
     * 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
     * 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
     * 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
     * 给你一个整数数组 nums ，找出 nums 的下一个排列。
     * <p>
     * 必须 原地 修改，只允许使用额外常数空间。
     * <p>
     * 示例 1：
     * <p>
     * 输入：nums = [1,2,3]
     * 输出：[1,3,2]
     */
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        /**
         *
         * 双指针：
         1： 从尾部开始找到第一个峰值 lastPeekIdx
         2： 找到峰值右边j比左边i大的最小元素，swap(i, j)
         然后reserver(lastPeekIdx, n - 1);
         */
        int n = nums.length;
        int lastPeekIdx = n - 1;
        while (lastPeekIdx > 0 && nums[lastPeekIdx] <= nums[lastPeekIdx - 1]) {
            lastPeekIdx--;
        }
        if (lastPeekIdx == 0) {
            reverse(nums, 0, n - 1);
            return;
        }
        int j = lastPeekIdx - 1;
        int i = n - 1;
        while (i >= lastPeekIdx) {
            if (nums[i] <= nums[j]) {
                i--;
            } else {
                swap(nums, i, j);
                break;
            }
        }
        reverse(nums, lastPeekIdx, n - 1);
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    private void reverse(int[] nums, int s, int e) {
        while (s < e) {
            swap(nums, s++, e--);
        }
    }

    /**
     * 78. 子集
     * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
     * <p>
     * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
     * <p>
     * 示例 1：
     * 输入：nums = [1,2,3]
     * 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return ans;
        }

        subsetsHelper(ans, nums, 0, new ArrayList<Integer>());
        return ans;
    }

    private void subsetsHelper(List<List<Integer>> ans, int[] nums, int startIdx, List<Integer> list) {

        ans.add(new ArrayList<>(list));

        for (int i = startIdx; i < nums.length; i++) {
            list.add(nums[i]);
            subsetsHelper(ans, nums, i + 1, list);
            list.remove(list.size() - 1);
        }
    }

    /**
     * 90. 子集 II
     * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
     * <p>
     * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
     * <p>
     * 示例 1：
     * <p>
     * 输入：nums = [1,2,2]
     * 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
     */
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return ans;
        }

        Arrays.sort(nums);
        subsetsWithDupHelper(ans, nums, 0, new ArrayList<Integer>());
        return ans;
    }

    private void subsetsWithDupHelper(List<List<Integer>> ans, int[] nums, int startIdx, List<Integer> list) {
        ans.add(new ArrayList<>(list));

        for (int i = startIdx; i < nums.length; i++) {

            // 依旧是树层去重
            if (i != startIdx && nums[i] == nums[i - 1]) {
                continue;
            }

            list.add(nums[i]);
            subsetsWithDupHelper(ans, nums, i + 1, list);
            list.remove(list.size() - 1);
        }
    }

    /**
     * 784. 字母大小写全排列
     * 给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。
     * <p>
     * 返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。
     * <p>
     * 示例 1：
     * <p>
     * 输入：s = "a1b2"
     * 输出：["a1b2", "a1B2", "A1b2", "A1B2"]
     */
    public List<String> letterCasePermutation(String s) {
        List<String> ans = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return ans;
        }

        char[] cs = s.toCharArray();

        letterCasePermutationHelper(ans, cs, 0);

        return ans;
    }

    private void letterCasePermutationHelper(List<String> ans, char[] cs, int startIdx) {
        ans.add(new String(cs));

        for (int i = startIdx; i < cs.length; i++) {
            char c = cs[i];
            if ('A' <= c && c <= 'z') {
                boolean big = c <= 'Z' && c >= 'A';
                c = cs[i];
                cs[i] = big ? (char) (c + gap) : (char) (c - gap);
                letterCasePermutationHelper(ans, cs, i + 1);
                cs[i] = c;
            }
        }
    }

    private static int gap = 'a' - 'A';

    /**
     * 3668 · 括号展开 (lintcode)
     * <p>
     * 给定一个字符串 s，按以下规则组成一个新的单词：
     * <p>
     * 若字母在花括号之外，则说明该字母在新单词的对应位置是一个必选字符
     * 若字母在花括号之内，则说明该字母在新单词的对应位置是一个选项字符
     * 花括号之内可能会存在多个字母，对于花括号内的所有选项字符，必须且只能选取其中一个
     * 按照以上规则，返回所有可以组成的新单词，并按照字典顺序进行排列。
     * <p>
     * s 不含有嵌套括号
     * <p>
     * 输入：
     * s = "a{b,c}"
     * 输出：
     * ["ab", "ac"]
     * 解释：
     * 第一个字符一定是 "a"，第二个字符可以是 "b" 或 "c"
     */
    public List<String> bracketExpansion(String s) {

        List<String> res = new ArrayList<>();

        if (s == null || s.length() == 0) {
            return res;
        }

        List<List<String>> lists = toList(s);

        bracketExpansionHelper(res, lists, new StringBuilder(), 0);

        return res;
    }

    private void bracketExpansionHelper(List<String> res, List<List<String>> lists, StringBuilder sb, int startIdx) {
        if (sb.length() == lists.size()) {
            res.add(sb.toString());
            return;
        }

        for (int i = startIdx; i < lists.size(); i++) {
            for (String s : lists.get(i)) {
                sb.append(s);
                bracketExpansionHelper(res, lists, sb, i + 1);
                sb.deleteCharAt(sb.length() - 1);
            }
        }
    }

    private List<List<String>> toList(String s) {
        List<List<String>> list = new ArrayList<>();
        int i = 0;
        while (i < s.length()) {
            List<String> tmp = new ArrayList<>();
            if (s.charAt(i) == '{') {
                int j = s.indexOf("}", i);
                if (j > 0) {
                    String[] split = s.substring(i + 1, j).split(",");
                    tmp = Arrays.asList(split);
                } else {
                    break;
                }
                i = j + 1;
            } else {
                tmp.add(s.charAt(i) + "");
                i++;
            }
            list.add(tmp);
        }

        return list;
    }

}

